package com.huangkailong.learning.datastructure.tree;

import com.huangkailong.learning.datastructure.common.Assert;

import java.util.Objects;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.function.BiConsumer;

/**
 * @author huangkl
 * @since 1.0.0
 */
public abstract class AbstractBinaryFindTree<K extends Comparable<K>, V> implements BinaryFindTree<K, V> {
    protected static abstract class Node<K extends Comparable<K>, V>{
        /**
         * 结点 key
         */
        K key;
        /**
         * 结点 value
         */
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        /**
         * 获取左孩子指针
         * 
         * @return 左孩子指针
         */
        abstract Node<K, V> getLeft();

        /**
         * 获取右孩子指针
         * 
         * @return 右孩子指针
         */
        abstract Node<K, V> getRight();
    }

    /**
     * 前序遍历
     *
     * @param biConsumer {@link BiConsumer}
     */
    @Override
    public void preorderTraverse(BiConsumer<K,V> biConsumer){
        doPreorderTraverse(getRoot(), biConsumer);
    }


    private void doPreorderTraverse(Node<K,V> root, BiConsumer<K,V> biConsumer){
        if(Objects.isNull(root)){
            return;
        }
        biConsumer.accept(root.key, root.value);
        doPreorderTraverse(root.getLeft(), biConsumer);
        doPreorderTraverse(root.getRight(), biConsumer);
    }

    /**
     * 中序遍历
     *
     * @param biConsumer {@link BiConsumer}
     */
    @Override
    public void inorderTraverse(BiConsumer<K,V> biConsumer){
        doInorderTraverse(getRoot(), biConsumer);
    }

    private void doInorderTraverse(Node<K,V> root, BiConsumer<K,V> biConsumer){
        if(Objects.isNull(root)){
            return;
        }
        doInorderTraverse(root.getLeft(), biConsumer);
        biConsumer.accept(root.key, root.value);
        doInorderTraverse(root.getRight(), biConsumer);
    }

    /**
     * 后序遍历
     *
     * @param biConsumer {@link BiConsumer}
     */
    @Override
    public void postorderTraverse(BiConsumer<K,V> biConsumer){
        doPostorderTraverse(getRoot(), biConsumer);
    }

    private void doPostorderTraverse(Node<K,V> root, BiConsumer<K,V> biConsumer){
        if(Objects.isNull(root)){
            return;
        }
        doPostorderTraverse(root.getLeft(), biConsumer);
        doPostorderTraverse(root.getRight(), biConsumer);
        biConsumer.accept(root.key, root.value);
    }

    /**
     * 层序遍历
     *
     * @param biConsumer {@link BiConsumer}
     */
    @Override
    public void levelTraverse(BiConsumer<K,V> biConsumer){
        doLevelTraverse(getRoot(), biConsumer);
    }

    private void doLevelTraverse(Node<K,V> root, BiConsumer<K,V> biConsumer){
        Queue<Node<K,V>> queue = new ConcurrentLinkedQueue<>();
        if(Objects.isNull(root)){
            return;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            final Node<K,V> node = queue.poll();
            biConsumer.accept(node.key, node.value);
            addIfNotNull(queue, node.getLeft());
            addIfNotNull(queue, node.getRight());
        }
    }

    private void addIfNotNull(Queue<Node<K,V>> queue, Node<K,V> left) {
        if (Objects.nonNull(left)) {
            queue.add(left);
        }
    }

    /**
     * 获取二叉查找树的高度
     *
     * @return 高度
     */
    @Override
    public int getHeight(){
        return height(getRoot());
    }

    private int height(Node<K,V> root){
        if(Objects.isNull(root)){
            return 0;
        }

        int lh = height(root.getLeft());
        int lr = height(root.getRight());

        return Math.max(lh, lr) + 1;
    }

    @Override
    public V get(K key) {
        Assert.isNotNull(key, "Key 不能为空!");
        if(isEmpty()){
            return null;
        }
        return doGet(key);
    }

    private V doGet(K key) {
        Node<K, V> p = getRoot();
        while (Objects.nonNull(p)){
            if(eq(key, p.key)){
                return p.value;
            }
            if(lt(key, p.key)){
                p = p.getLeft();
            }else {
                p = p.getRight();
            }
        }
        return null;
    }

    /**
     * 获取二叉查找树的根结点
     *
     * @return 二叉查找树的根结点
     */
    protected abstract Node<K, V> getRoot();

    /**
     * k1 是否小于 k2
     *
     * @param k1 k1
     * @param k2 k2
     * @return k1 小于 k2 返回true
     */
    protected boolean lt(K k1, K k2){
        return k1.compareTo(k2) < 0;
    }

    /**
     * k1 是否等于 k2
     *
     * @param k1 k1
     * @param k2 k2
     * @return k1 等于 k2 返回 true
     */
    protected boolean eq(K k1, K k2){
        return k1.compareTo(k2) == 0;
    }

    /**
     * k1 是否大于 k2
     *
     * @param k1 k1
     * @param k2 k2
     * @return k1 大于 k2 返回 true
     */
    protected boolean gt(K k1, K k2){
        return k1.compareTo(k2) > 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        inorderTraverse((k,v)->{
            sb.append(k).append("=").append(v).append(",");
        });
        if(sb.toString().endsWith(",")){
            sb.delete(sb.length()-1, sb.length());
        }
        sb.append("}");

        return sb.toString();
    }
}
